This invention relates to an interconnection network with a self-routing function suitable for use with an ATM exchange.
The demand for higher speed, broader band communication networks has been and is increasing, and much attention is paid to an asynchronous transmission mode (ATM) as a communication system of the next generation. Thus, an interconnection network which has a self-routing function to effect autonomous routing by hardware and is anticipated to achieve a high speed operation is considered promising as means to realize an ATM exchange.
However, in a Batcher-banyan network which is one of interconnection networks of the self-routing type, the latency by routing processing depends upon the numbers of stages of the Batcher sorting network and the banyan routing network. Consequently, realization of an interconnection network of the self-routing type which is more suitable for an ATM exchange and has a reduced number of stages, that is, has a reduced latency is demanded.
FIG. 20 is a block diagram showing a Batcher-banyan network. Referring to FIG. 20, the Batcher-banyan network 70 shown has a self-routing function with N (N=2.sup.n, n is a natural number) input and output lines. The Batcher-banyan network 70 includes a Batcher sorting network 71, a comparison/blocking circuit 72, a concentration circuit 73, and a banyan network 74.
The Batcher sorting network 71 has N inputs and N outputs and is constituted from n(n+1)/2 stages (n=log.sub.2 N). The Batcher sorting network 71 effects sorting of cells.
The comparison/blocking circuit 72 has N inputs and N outputs and compares addresses of cells sorted by the Batcher sorting network 71 to block inactive cells.
The concentration circuit 73 has N inputs and N outputs and compensates for blocked cells and then concentrates the cells.
The banyan network 74 has N inputs and N outputs and outputs listed cells to the corresponding output lines based on destination address information of the cells.
In the Batcher-banyan network 70 of the construction described above, inputted cells are rearranged based on the magnitude of destination address information of them (such re-arrangement will be hereinafter referred to as sorting) by the Batcher sorting network 71. As a result of the sorting, those cells having an identical destination address are listed continuously.
Then, the comparison/blocking circuit 72 compares the addresses of the cells and leaves only one of those cells having an Identical address while purging the remaining Cells (such purging will be hereinafter referred to as blocking). Then, when blocking of cells is performed, the list of the cells is discontinuous, and therefore, the cells are passed through the concentration circuit 73 to pack them so that they may be listed continuously.
The sequence of the cells sorted based on the destination addresses thereof and packed into the continuous list In this manner are inputted to the banyan network 74. The banyan network 74 thus outputs the cells to the output lines thereof corresponding to the destination addresses (this will be hereinafter described as routing).
In such an interconnection network with a self-routing function as described above, however, the number of stages, upon which the latency by routing processing depends, is a total of n(n+3)/2 stages with the Batcher sorting network and the banyan network.
Accordingly, If it is assumed that the processing time per one bit of information is represented as 1 bit-time, then the processing time of 1 bit-time is required per one stage. Accordingly, in the Batcher sorting network and the banyan network, the processing time of a total of n(n+3)/2 bit-times is required, and this occupies a larger part of the latency.
Therefore, when a Batcher-banyan network is applied to an ATM exchange for use for high speed broad band communication, since conventional Batcher-banyan networks have a comparatively large number of stages, they have a subject to be solved that the latency by routing processing is long.